package 周赛;

public class 统计特殊子序列的数目 {

    //思路
//    因为只要下标集合不同就是不同的子序列，所以我们不存在重复的子序列。因此，我们只要记录当前的0串数目、01串数目
//    和012串数目即可。
//
//    因为我们可以从0串得到0串和01串，从01串得到01串和012串，从012串得到012串，所以转移是很清晰的：
//
//    如果当前位是0，则可以增加zero+1个0串；
//    如果当前位是1，则可以增加zero+one个01串；
//    如果当前位是2，则可以增加one+two个012串。
        public int countSpecialSubsequences(int[] nums) {
             int mod=1000000007;
             long zero=0,one=0,two=0;
            for (int num : nums) {
                if (num==0) {
                    zero += zero + 1;
                    zero%=mod;
                }
                if (num==1) {
                    one += zero + one;
                    one%=mod;
                }
                if (num==2) {
                    two += one + two;
                    two%=mod;
                }
            }
            return (int) two;
        }
}
